//如果我们可以将小写字母插入模式串 pattern 得到待查询项 query，那么待查询项与给定模式串匹配。（我们可以在任何位置插入每个字符，也可以插入 0 
//个字符。） 
//
// 给定待查询列表 queries，和模式串 pattern，返回由布尔值组成的答案列表 answer。只有在待查项 queries[i] 与模式串 patt
//ern 匹配时， answer[i] 才为 true，否则为 false。 
//
// 
//
// 示例 1： 
//
// 输入：queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"]
//, pattern = "FB"
//输出：[true,false,true,true,false]
//示例：
//"FooBar" 可以这样生成："F" + "oo" + "B" + "ar"。
//"FootBall" 可以这样生成："F" + "oot" + "B" + "all".
//"FrameBuffer" 可以这样生成："F" + "rame" + "B" + "uffer". 
//
// 示例 2： 
//
// 输入：queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"]
//, pattern = "FoBa"
//输出：[true,false,true,false,false]
//解释：
//"FooBar" 可以这样生成："Fo" + "o" + "Ba" + "r".
//"FootBall" 可以这样生成："Fo" + "ot" + "Ba" + "ll".
// 
//
// 示例 3： 
//
// 输出：queries = ["FooBar","FooBarTest","FootBall","FrameBuffer","ForceFeedBack"]
//, pattern = "FoBaT"
//输入：[false,true,false,false,false]
//解释： 
//"FooBarTest" 可以这样生成："Fo" + "o" + "Ba" + "r" + "T" + "est".
// 
//
// 
//
// 提示： 
//
// 
// 1 <= queries.length <= 100 
// 1 <= queries[i].length <= 100 
// 1 <= pattern.length <= 100 
// 所有字符串都仅由大写和小写英文字母组成。 
// 
// Related Topics 字典树 字符串 
// 👍 22 👎 0

package com.leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

//Java：驼峰式匹配
class P1023CamelcaseMatching {
    public static void main(String[] args) {
        Solution solution = new P1023CamelcaseMatching().new Solution();
        // TO TEST
        System.out.println(solution.check("FaFeedBack", "FeB"));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Boolean> camelMatch(String[] queries, String pattern) {
            List<Boolean> ans = new ArrayList<>();
            for (String query : queries) {
                ans.add(check(query, pattern));
            }
            return ans;
        }

        private boolean check(String query, String pattern) {
            char[] queryChar = query.toCharArray();
            char[] patternChar = pattern.toCharArray();
            int patternIndex = 0;
            int queryIndex = 0;
            while (patternIndex < patternChar.length) {
                //如果模式串还有值，待查询项已经越界(Fo,F)那么直接返回false
                if (queryIndex >= queryChar.length) {
                    return false;
                }
                while (queryIndex < queryChar.length) {
                    //查询项指针后移，直到在查询项中找到当前匹配字符
                    if (queryChar[queryIndex++] == patternChar[patternIndex]) {
                        patternIndex++;
                        break;
                    }
                    //因为只能插入小写字母，所以在查询项中找到匹配字符之前，查找到了大写字母，那么就不能匹配，直接返回false
                    if (queryChar[queryIndex - 1] - 'a' < 0) {
                        return false;
                    }
                }
            }
            //因为只能插入小写字母，匹配串全部处理完，查询项指针后边还有值，那么判断剩下的字符里边有没有大写，如果有，直接返回false
            while (queryIndex < queryChar.length) {
                if (queryChar[queryIndex++] - 'a' < 0) {
                    return false;
                }
            }
            return true;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}